{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #套餐内商品的排列顺序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: goodsOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #套餐内商品的排列顺序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某店铺将用于组成套餐的商品记作字符串 <code>goods</code>，其中 <code>goods[i]</code> 表示对应商品。请返回该套餐内所含商品的 <strong>全部排列方式</strong> 。</p>\n",
    "\n",
    "<p>返回结果 <strong>无顺序要求</strong>，但不能含有重复的元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>goods = \"agew\"\n",
    "<strong>输出：</strong>[\"aegw\",\"aewg\",\"agew\",\"agwe\",\"aweg\",\"awge\",\"eagw\",\"eawg\",\"egaw\",\"egwa\",\"ewag\",\"ewga\",\"gaew\",\"gawe\",\"geaw\",\"gewa\",\"gwae\",\"gwea\",\"waeg\",\"wage\",\"weag\",\"wega\",\"wgae\",\"wgea\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= goods.length &lt;= 8</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zi-fu-chuan-de-pai-lie-lcof](https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zi-fu-chuan-de-pai-lie-lcof](https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, s: str) -> List[str]:\n",
    "        res = ['']\n",
    "        for i in s:\n",
    "            tmp = []\n",
    "            for j in res:\n",
    "                for k in range((j+i).index(i)+1):\n",
    "                    tmp.append(j[:k]+i+j[k:])\n",
    "            res = tmp\n",
    "        return res\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        ans = ['']\n",
    "        for c in goods:\n",
    "            ans = [word[:i]+c+word[i:] for word in ans for i in range((word+c).index(c)+1)]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        # c, res = list(goods), []\n",
    "        # def dfs(x):\n",
    "        #     if x == len(c) - 1:\n",
    "        #         res.append(''.join(c))\n",
    "        #         return\n",
    "        #     dic = set()\n",
    "        #     for i in range(x, len(c)):\n",
    "        #         if c[i] in dic: continue\n",
    "        #         dic.add(c[i])\n",
    "        #         c[i], c[x] = c[x], c[i]\n",
    "        #         dfs(x+1)\n",
    "        #         c[i], c[x] = c[x], c[i]\n",
    "        # dfs(0)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def backtrack(\n",
    "            state: list[str],\n",
    "            choices: list[str],\n",
    "            selected: list[bool],\n",
    "            results: list[str],\n",
    "        ):\n",
    "            # is solution?\n",
    "            if len(state) == len(choices):\n",
    "                results.append(\"\".join(state))\n",
    "                return\n",
    "            duplicated = set[int]()  # for current loop only\n",
    "            for idx, choice in enumerate(choices):\n",
    "                if not selected[idx] and choice not in duplicated:\n",
    "                    # make choice\n",
    "                    state.append(choice)\n",
    "                    selected[idx] = True\n",
    "                    duplicated.add(choice)\n",
    "                    # next round\n",
    "                    backtrack(state, choices, selected, results)\n",
    "                    # undo choice\n",
    "                    state.pop()\n",
    "                    selected[idx] = False\n",
    "\n",
    "        state = []\n",
    "        choices = list(goods)\n",
    "        selected = [False] * len(goods)\n",
    "        results = []\n",
    "        backtrack(state, choices, selected, results)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def backtrack(state, selected, choices, res):\n",
    "            if len(state) == len(goods):\n",
    "                res.append(''.join(_ for _ in state))\n",
    "            duplicated = set()\n",
    "            for i, choice in enumerate(choices):\n",
    "                if not selected[i] and choice not in duplicated:\n",
    "                    duplicated.add(choice)\n",
    "                    selected[i] = True\n",
    "                    state.append(choice)\n",
    "                    backtrack(state, selected, choices, res)\n",
    "                    selected[i] = False\n",
    "                    state.pop()\n",
    "            \n",
    "        res = []\n",
    "        backtrack([], [False] * len(goods), goods, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        used=[False]*len(goods)\n",
    "        def f(goods,path,res):\n",
    "            if len(path)==len(goods):\n",
    "                if path not in res:\n",
    "                    res.append(path)\n",
    "                return\n",
    "            for i in range(len(goods)):\n",
    "                if used[i]==True:\n",
    "                    continue\n",
    "                path+=goods[i]\n",
    "                used[i]=True\n",
    "                f(goods,path,res)\n",
    "                used[i]=False\n",
    "                path=path[:-1]\n",
    "        path=''\n",
    "        res=[]\n",
    "        f(goods,path,res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = \"\"\n",
    "        self.used = []\n",
    "\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        self.permuteUnique(list(goods))\n",
    "        arr = [None] * len(self.res)\n",
    "        for i in range(len(self.res)):\n",
    "            arr[i] = self.res[i]\n",
    "        return arr\n",
    "\n",
    "    def permuteUnique(self, nums):\n",
    "        nums.sort()\n",
    "        self.used = [False] * len(nums)\n",
    "        self.backtrack(nums)\n",
    "\n",
    "    def backtrack(self, nums):\n",
    "        if len(nums) == len(self.track):\n",
    "            self.res.append(self.track)\n",
    "            return\n",
    "        for i in range(len(nums)):\n",
    "            if self.used[i]:\n",
    "                continue\n",
    "            if i > 0 and nums[i] == nums[i-1] and not self.used[i-1]:\n",
    "                continue\n",
    "            self.track += nums[i]\n",
    "            self.used[i] = True\n",
    "            self.backtrack(nums)\n",
    "            self.track = self.track[:-1]\n",
    "            self.used[i] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def goodsOrder(self, goods: str) -> List[str]:\n",
    "\n",
    "#         def combination(chars:List)->List[str]:\n",
    "#             if len(chars) <= 1: return chars\n",
    "#             res = []\n",
    "#             unique_char = set(chars)\n",
    "#             unique_indx = [chars.index(c) for c in unique_char]\n",
    "#             for i in unique_indx:\n",
    "#                 prefix = chars[i]\n",
    "#                 sub_chars = chars[0:i] + chars[(i+1):]\n",
    "#                 sub_res = combination(sub_chars)\n",
    "#                 sub_res = [\"\".join([prefix, sub]) for sub in sub_res]\n",
    "#                 res.extend(sub_res)\n",
    "#             return res\n",
    "\n",
    "#         chars = list(goods)\n",
    "#         res = combination(chars)\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "\n",
    "        def combination(chars:List)->List[str]:\n",
    "            if len(chars) <= 1: return chars\n",
    "            res = []\n",
    "            unique_char = set(chars)\n",
    "            unique_indx = [chars.index(c) for c in unique_char]\n",
    "            for i in unique_indx:\n",
    "                prefix = chars[i]\n",
    "                sub_chars = chars[0:i] + chars[(i+1):]\n",
    "                sub_res = combination(sub_chars)\n",
    "                sub_res = [\"\".join([prefix, sub]) for sub in sub_res]\n",
    "                res.extend(sub_res)\n",
    "            return res\n",
    "\n",
    "        chars = list(goods)\n",
    "        res = combination(chars)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        goods = sorted(goods)\n",
    "        n = len(goods)\n",
    "        path = ['']*n\n",
    "        ans = []\n",
    "        t = [False]*n\n",
    "        b = False \n",
    "        def dfs(d:int):\n",
    "            nonlocal b\n",
    "            if d == n:\n",
    "                ans.append(''.join(path.copy()))\n",
    "                return \n",
    "            for k,v in enumerate(goods):\n",
    "                if t[k] == False:\n",
    "                    if b and k > 0 and goods[k] == path[d]:\n",
    "                        continue\n",
    "                    b = False\n",
    "                    t[k] = True \n",
    "                    path[d] = goods[k]\n",
    "                    dfs(d+1)\n",
    "                    t[k] = False\n",
    "                    b = True\n",
    "        dfs(0)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        goods = list(goods)\n",
    "        goods.sort()\n",
    "\n",
    "        def dfs(res, path, k, goods):\n",
    "            if k==0:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i in range(len(goods)):\n",
    "                if i and goods[i]==goods[i-1]:\n",
    "                    continue\n",
    "                dfs(res, path+[goods[i]],k-1,goods[:i]+goods[i+1:])\n",
    "        res = []\n",
    "        path = []\n",
    "        dfs(res, path, len(goods), goods)\n",
    "        for i in range(len(res)):\n",
    "            res[i] = \"\".join(res[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "\n",
    "        # 遍历 \n",
    "        '''\n",
    "        def add_str(string, target_r):\n",
    "            out_str = [target_r + string]\n",
    "\n",
    "            for i in range(0+1,len(string)+1):\n",
    "                s = string[0:i] + target_r + string[i:]\n",
    "                out_str.append(s)\n",
    "            return out_str\n",
    "\n",
    "        if goods == '':\n",
    "            return ''\n",
    "        if len(goods) == 1:\n",
    "            return [goods]\n",
    "\n",
    "        output = []\n",
    "        for i in range(len(goods)):\n",
    "            if output == []:\n",
    "                output.append(goods[i])\n",
    "            else:\n",
    "                output_temp = []\n",
    "                for str_j in output:\n",
    "                    # 在每一个字符串中添加新的字符\n",
    "                    temp = add_str( str_j,goods[i])\n",
    "                    output_temp = output_temp + temp\n",
    "                output = output_temp\n",
    "\n",
    "        used = []\n",
    "        for i in output:\n",
    "            if i not in used:\n",
    "                used.append(i)\n",
    "        return used   \n",
    "        '''     \n",
    "\n",
    "        # c, res = list(goods), []\n",
    "        # def dfs(x):\n",
    "        #     if x == len(c) - 1:\n",
    "        #         res.append(''.join(c))   # 添加排列方案\n",
    "        #         return\n",
    "        #     dic = set()\n",
    "        #     for i in range(x, len(c)):\n",
    "        #         if c[i] in dic: continue # 重复，因此剪枝\n",
    "        #         dic.add(c[i])\n",
    "        #         c[i], c[x] = c[x], c[i]  # 交换，将 c[i] 固定在第 x 位\n",
    "        #         dfs(x + 1)               # 开启固定第 x + 1 位字符\n",
    "        #         c[i], c[x] = c[x], c[i]  # 恢复交换\n",
    "        # dfs(0)\n",
    "        # return res\n",
    "\n",
    "\n",
    "        \n",
    "        def get_s(string):\n",
    "            if string == \"\": return [\"\"]\n",
    "            if len(string) == 1:\n",
    "                return [string]\n",
    "            else:\n",
    "                temp_out = []\n",
    "                for i in range(0, len(string)):\n",
    "                    string = list(string)\n",
    "                    if string[0] == string[i] and i !=0:\n",
    "                        string = ''.join(string)\n",
    "                        continue\n",
    "                    else:\n",
    "                        string[0], string[i] = string[i], string[0]\n",
    "                        string = ''.join(string)\n",
    "                        temp_s = get_s(string[1:])\n",
    "                        # print(string, temp_s)\n",
    "                        for s_i in range(len(temp_s)):\n",
    "                            temp_s[s_i] = string[0] + temp_s[s_i]\n",
    "                        temp_out = temp_out + temp_s\n",
    "                return temp_out\n",
    "       \n",
    "        if goods == '': return ['']\n",
    "        out_temp = get_s(goods)\n",
    "        # return out_temp\n",
    "        used = []\n",
    "        for i in out_temp:\n",
    "            if i not in used:\n",
    "                used.append(i)\n",
    "        return used \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        return list(set(\"\".join(i) for i in itertools.permutations(goods) ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def dfs(goods, depth, path, used, res):\n",
    "            if depth == n:\n",
    "                res.add(\"\".join(path[:]))\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                path.append(goods[i])\n",
    "                used[i] = True\n",
    "                dfs(goods, depth+1, path, used, res)\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "        \n",
    "        if len(goods) == 0: return []\n",
    "        n = len(goods)\n",
    "        res = set()\n",
    "        \n",
    "        path = []\n",
    "        used = [False for _ in range(n)]\n",
    "        dfs(goods, 0, path, used, res)\n",
    "\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def dfs(goods, depth, path, used, res):\n",
    "            if depth == n:\n",
    "                res.add(\"\".join(path[:]))\n",
    "                return\n",
    "\n",
    "            for i in range(n):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                path.append(goods[i])\n",
    "                used[i] = True\n",
    "                dfs(goods, depth+1, path, used, res)\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "\n",
    "        n = len(goods)\n",
    "        res = set()\n",
    "        if n == 0: return list(res)\n",
    "        \n",
    "        path = []\n",
    "        used = [False for _ in range(n)]\n",
    "        dfs(goods, 0, path, used, res)\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        if len(goods) == 1:\n",
    "            return [goods]\n",
    "        res = set()\n",
    "        c_0 = goods[0]\n",
    "        c_rest = self.goodsOrder(goods[1:])\n",
    "        for item in c_rest:\n",
    "            for index in range(len(item)+1):\n",
    "                res.add(item[:index]+c_0+item[index:])\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        if len(goods) == 1:\n",
    "            return [goods]\n",
    "        res = set()\n",
    "        c_1 = goods[0]\n",
    "        c_rest = self.goodsOrder(goods[1:])\n",
    "        for c_n in c_rest:\n",
    "            for index in range(len(c_n)+1):\n",
    "                res.add(\n",
    "                    c_n[:index]+c_1+c_n[index:]\n",
    "                )\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def add_str(string, target_r):\n",
    "            out_str = [target_r + string]\n",
    "\n",
    "            for i in range(0+1,len(string)+1):\n",
    "                s = string[0:i] + target_r + string[i:]\n",
    "                out_str.append(s)\n",
    "            return out_str\n",
    "\n",
    "        if goods == '':\n",
    "            return ''\n",
    "        if len(goods) == 1:\n",
    "            return [goods]\n",
    "\n",
    "        output = []\n",
    "        for i in range(len(goods)):\n",
    "            if output == []:\n",
    "                output.append(goods[i])\n",
    "            else:\n",
    "                output_temp = []\n",
    "                for str_j in output:\n",
    "                    # 在每一个字符串中添加新的字符\n",
    "                    temp = add_str( str_j,goods[i])\n",
    "                    output_temp = output_temp + temp\n",
    "                output = output_temp\n",
    "\n",
    "\n",
    "        used = []\n",
    "        for i in output:\n",
    "            if i not in used:\n",
    "                used.append(i)\n",
    "        return used        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        n = len(goods)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        g = list(goods)\n",
    "        g.sort()\n",
    "        ans = []\n",
    "        path = []\n",
    "        visited = [False] * n\n",
    "        def dfs():\n",
    "            if len(path) == n:\n",
    "                ans.append(''.join(path.copy()))\n",
    "                return\n",
    "            \n",
    "            for x in range(n):\n",
    "                if x > 0 and g[x] == g[x - 1] and not visited[x - 1]:\n",
    "                    continue\n",
    "                if not visited[x]:\n",
    "                    visited[x] = True\n",
    "                    path.append(g[x])\n",
    "                    dfs()\n",
    "                    path.pop()\n",
    "                    visited[x] = False\n",
    "        \n",
    "        dfs()\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        nums= list(goods)\n",
    "        nums.sort()\n",
    "\n",
    "        n =len(nums)\n",
    "        path=[]\n",
    "        ans =[]\n",
    "        used =[0]*n\n",
    "\n",
    "        # 位置大于等于i的部分还要枚举\n",
    "        def dfs(i):\n",
    "            if len(path)==n:\n",
    "                ans.append(''.join(path.copy()))\n",
    "            \n",
    "            for j in range(n):\n",
    "                if not used[j]:\n",
    "                    if j>0 and nums[j]==nums[j-1] and used[j-1]==0:\n",
    "                        continue\n",
    "                    path.append(nums[j])\n",
    "                    used[j]=1\n",
    "                    dfs(i+1)\n",
    "                    path.pop()\n",
    "                    used[j]=0\n",
    "            \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        if len(goods)<=1:\n",
    "            return [goods]\n",
    "        res=set()\n",
    "        for i in range(len(goods)):\n",
    "            for j in self.goodsOrder(goods[0:i]+goods[i+1:]):\n",
    "                res.add(j+goods[i])\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def dfs(s:str):\n",
    "            if not s: return ['']\n",
    "            res = set()\n",
    "\n",
    "            for i in range(len(s)):\n",
    "                for j in dfs(s[:i] + s[i + 1:]):\n",
    "                    res.add(s[i] + j)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return list(dfs(goods))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def arrange(s):         \n",
    "            if s == \"\":\n",
    "                return [\"\"]\n",
    "\n",
    "            result = []\n",
    "            for char in s:\n",
    "                resultListSub = arrange(s.replace(char, '', 1))\n",
    "                for subResult in resultListSub:\n",
    "                    result.append(char + subResult)\n",
    "        \n",
    "            return list(set(result))\n",
    "\n",
    "        return arrange(goods)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        tmp, res = list(goods), []\n",
    "        def backtrack(x):\n",
    "            if x == len(tmp) - 1 and \"\".join(tmp) not in res:\n",
    "                res.append(\"\".join(tmp))\n",
    "                return\n",
    "            goods_set = set()\n",
    "            for i in range(x, len(goods)):\n",
    "                if tmp[i] in goods_set:\n",
    "                    continue\n",
    "                goods_set.add(tmp[i])\n",
    "                tmp[x], tmp[i] = tmp[i], tmp[x]\n",
    "                backtrack(x + 1)\n",
    "                tmp[x], tmp[i] = tmp[i], tmp[x]\n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        tmp, res = list(goods), []\n",
    "        def dfs(x):\n",
    "            if x == len(tmp) - 1:\n",
    "                res.append(\"\".join(tmp))\n",
    "            tmp_set = set()\n",
    "            for i in range(x, len(goods)):\n",
    "                if tmp[i] in tmp_set:\n",
    "                    continue\n",
    "                tmp_set.add(tmp[i])\n",
    "                tmp[i], tmp[x] = tmp[x], tmp[i]\n",
    "                dfs(x + 1)\n",
    "                tmp[i], tmp[x] = tmp[x], tmp[i]\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import itertools\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        l = []\n",
    "        for i in itertools.permutations(goods,len(goods)):\n",
    "            l.append(''.join(i))\n",
    "        templ = set(l)\n",
    "        return list(templ)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from itertools import permutations\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        l = []\n",
    "        for i in permutations(goods,len(goods)):\n",
    "            l.append(''.join(i))\n",
    "        templ = set(l)\n",
    "        return list(templ)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        l=[]\n",
    "        for i in itertools.permutations(goods,len(goods)):\n",
    "            tmp = \"\".join(i)\n",
    "            l.append(tmp)\n",
    "        l = set(l)\n",
    "        return list(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        arr, res = list(goods), []\n",
    "\n",
    "        def dfs(x):\n",
    "            if x == len(arr) - 1:\n",
    "                res.append(\"\".join(arr))\n",
    "            hmap = set()\n",
    "            for i in range(x, len(arr)):\n",
    "                print(\"i\", i)\n",
    "                if arr[i] in hmap:\n",
    "                    continue\n",
    "                hmap.add(arr[i])\n",
    "                # 交换，将 arr[i] 固定在第 x 位\n",
    "                arr[i], arr[x] = arr[x], arr[i]\n",
    "                # 开启固定第 x + 1 位字符\n",
    "                dfs(x + 1)\n",
    "                # 恢复交换\n",
    "                arr[i], arr[x] = arr[x], arr[i]\n",
    "\n",
    "        dfs(0)\n",
    "        print(res)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        return list( set( [\"\".join(i) for i in itertools.permutations(goods) ] ))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def check(s: str):\n",
    "            if len(s) <= 1:\n",
    "                return [s]\n",
    "            ans = []\n",
    "            for i in range(len(s)):\n",
    "                for j in check(s[0:i] + s[i + 1:]):\n",
    "                    # print(s[i],j,s[i] + j)\n",
    "                    ans.append(s[i] + j)\n",
    "            return ans\n",
    "\n",
    "        res = list(set(check(goods)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        if len(goods) == 1:\n",
    "            return [goods]\n",
    "        res = []\n",
    "        c_1 = goods[0]\n",
    "        c_rest = self.goodsOrder(goods[1:])\n",
    "        for c_n in c_rest:\n",
    "            for index in range(len(c_n)+1):\n",
    "                res.append(\n",
    "                    c_n[:index]+c_1+c_n[index:]\n",
    "                )\n",
    "        return list(set(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, s: str) -> List[str]:\n",
    "        if not s:\n",
    "            return []\n",
    "        return list(sorted(set(self.helper(list(s)))))\n",
    "\n",
    "    def helper(self, s):\n",
    "        if len(s) == 1:\n",
    "            return s[0]\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            mid_res = self.helper(s[:i] + s[i+1:])\n",
    "            for j in mid_res:\n",
    "                res.append(s[i] + j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, s: str) -> List[str]:\n",
    "        # s = sorted(s)\n",
    "        # print(s)\n",
    "        paths  = []\n",
    "        self.cur = ''\n",
    "        vis = set()\n",
    "        def dfs(i):\n",
    "            if len(self.cur)==len(s) and self.cur not in paths:\n",
    "                paths.append(self.cur[:])\n",
    "                return\n",
    "            for j in range(len(s)):\n",
    "                if j>0 and s[j]==s[j-1] and j-1 not in vis:\n",
    "                    continue\n",
    "                if j not in vis:\n",
    "                    vis.add(j)\n",
    "                    self.cur += s[j]\n",
    "                    dfs(j+1)\n",
    "                    self.cur = self.cur[:-1]\n",
    "                    vis.remove(j)\n",
    "        dfs(0)\n",
    "        return [''.join(c) for c in paths]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        # 使用 itertools 中的 permutations 函数生成所有商品的排列方式\n",
    "        all_permutations = set(permutations(goods))\n",
    "        # 将排列方式转换为字符串并返回，去除重复项\n",
    "        return [''.join(p) for p in all_permutations]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, s: str) -> List[str]:\n",
    "        s = sorted(s)\n",
    "        # print(s)\n",
    "        paths  = []\n",
    "        self.cur = []\n",
    "        vis = set()\n",
    "        def dfs(i):\n",
    "            if len(self.cur)==len(s):\n",
    "                paths.append(self.cur[:])\n",
    "                return\n",
    "            for j in range(len(s)):\n",
    "                if j>0 and s[j]==s[j-1] and j-1 not in vis:\n",
    "                    continue\n",
    "                if j not in vis:\n",
    "                    vis.add(j)\n",
    "                    self.cur.append(s[j])\n",
    "                    dfs(j+1)\n",
    "                    self.cur.pop()\n",
    "                    vis.remove(j)\n",
    "        dfs(0)\n",
    "        return [''.join(c) for c in paths]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        val = \"\"\n",
    "        l = []\n",
    "        def resgoods(goods, val):\n",
    "            if(len(goods) == 0):\n",
    "                l.append(val)\n",
    "                return\n",
    "            for i in range(len(val)+1):\n",
    "                if i == 0:\n",
    "                    resgoods(goods[1:], goods[0] + val)\n",
    "                elif i == len(val):\n",
    "                    resgoods(goods[1:], val + goods[0])\n",
    "                else:\n",
    "                    resgoods(goods[1:], val[:i] + goods[0] + val[i:])\n",
    "            return\n",
    "        resgoods(goods, val)\n",
    "        l = list(set(l))\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        ans=[]\n",
    "        len_s=len(goods)\n",
    "        forb=[False]*len_s\n",
    "        print(forb)\n",
    "        def dfs(deep,str_):\n",
    "            if deep==len_s:\n",
    "                ans.append(str_)\n",
    "                return\n",
    "            for i in range(len_s):\n",
    "                if not forb[i]:\n",
    "                    forb[i]=True\n",
    "                    str_now=str_+goods[i]\n",
    "                    dfs(deep+1,str_now)\n",
    "                    forb[i]=False\n",
    "            return\n",
    "        dfs(0,'')\n",
    "        ans=list(set(ans))\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        gd = list(goods)\n",
    "        def dfs(x):\n",
    "            if x == len(gd)-1:\n",
    "                res.append(''.join(list(gd)))\n",
    "                return \n",
    "            for i in range(x, len(gd)):\n",
    "                if i > x and gd[i] == gd[x]:\n",
    "                    continue\n",
    "                gd[i], gd[x] = gd[x], gd[i]\n",
    "                dfs(x+1)\n",
    "                gd[i], gd[x] = gd[x], gd[i]\n",
    "        res = []\n",
    "        dfs(0)\n",
    "    \n",
    "        return list(set(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def dfs(goods,lenth,rr):\n",
    "            if lenth == len(goods):\n",
    "                res.add(\"\".join(rr))\n",
    "                return\n",
    "            dic = set()\n",
    "                \n",
    "            for i in range(lenth,len(goods)):\n",
    "                if goods[i] in dic:\n",
    "                    continue\n",
    "                rr.append(goods[i])\n",
    "                goods[lenth],goods[i] = goods[i],goods[lenth]\n",
    "                dfs(goods,lenth+1,rr)\n",
    "                goods[lenth],goods[i] = goods[i],goods[lenth]\n",
    "                rr.pop()\n",
    "        res = set()\n",
    "        dfs(list(goods),0,[])\n",
    "        return list(res)\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        def dfs(goods,lenth):\n",
    "            if lenth == len(goods):\n",
    "                res.add(\"\".join(goods))\n",
    "                return\n",
    "            dic = set()\n",
    "            for i in range(lenth,len(goods)):\n",
    "                if goods[i] in dic:\n",
    "                    continue  \n",
    "                dic.add(goods[i])   \n",
    "                goods[lenth],goods[i] = goods[i],goods[lenth]\n",
    "                dfs(goods,lenth+1)\n",
    "                goods[lenth],goods[i] = goods[i],goods[lenth]\n",
    "        res = set()\n",
    "        dfs(list(goods),0)\n",
    "        return list(res)\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        n = len(goods)\n",
    "        ans = set()\n",
    "        if n == 0:\n",
    "            return list(ans)\n",
    "        visited = [False] * n\n",
    "        path = []\n",
    "        def helper():\n",
    "            if len(path) == n:\n",
    "                ans.add(\"\".join(path))\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    visited[i] = True\n",
    "                    path.append(goods[i])\n",
    "                    helper()\n",
    "                    path.pop()\n",
    "                    visited[i] = False\n",
    "        helper()\n",
    "        return list(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodsOrder(self, goods: str) -> List[str]:\n",
    "        ans = set()\n",
    "        n = len(goods)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        visited = [False] * n\n",
    "        path = []\n",
    "        def helper():\n",
    "            if len(path) == n:\n",
    "                ans.add(\"\".join(path))\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    visited[i] = True\n",
    "                    path.append(goods[i])\n",
    "                    helper()\n",
    "                    path.pop()\n",
    "                    visited[i] = False\n",
    "        helper()\n",
    "        return list(ans)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
